package com.leetcode;


/**
 * 1139. 最大的以 1 为边界的正方形 (中等)
 * 给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
 */
public class LeetCode1139 {

    public static void main(String[] arg0) {
        int[][] grid = new int[3][3];
        grid[0] = new int[]{1, 1, 1};
        grid[1] = new int[]{1, 0, 1};
        grid[2] = new int[]{1, 1, 1};
        System.out.println("由 1 组成的最大 正方形 子网格元素数量 = " + largest1BorderedSquare(grid));
    }

    /**
     * 格子数组的宽高最大是100，所以正方形中的元素最多也就 100 * 100 = 10000
     */
    public static int largest1BorderedSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length; // 二维数组的行列数

        // 动态规划的两个数组
        int[][] left = new int[m + 1][n + 1];
        int[][] up = new int[m + 1][n + 1];

        int maxBorder = 0; // 最大正方形的边长
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (grid[i - 1][j - 1] == 1) {
                    left[i][j] = left[i][j - 1] + 1;
                    up[i][j] = up[i - 1][j] + 1;

                    int border = Math.min(left[i][j], up[i][j]);
                    while (left[i - border + 1][j] < border || up[i][j - border + 1] < border) {
                        border--;
                    }

                    maxBorder = Math.max(maxBorder, border);
                }
            }
        }

        return maxBorder * maxBorder;
    }

}
